
%----------------------
%      二次剩余
%----------------------

%\chapter{二次剩余}
中学学过的一元二次方程理论，讨论了实系数的一元二次方程的根如何求解。但到目前为止，人们还没有找到一般方法求解一般的多项式同余方程。除了求根问题，还有一个相关问题就是判断是否有解。二次同余方程有着较多的研究成果，这就是本节所涉及到的核心内容。

\section{二次同余方程}
二次同余方程的一般表达式为：$ax^2+bx+c \equiv 0(mod\ m),a\nequiv 0(mod\ m) $，下面我们讨论一般二次同余方程解的问题，讨论过程主要参考\cite{min2003}(第73页).\par
对于一个二次同余方程，有可能有解，有可能无解，例如$x^2-3 \equiv 0(mod\ 7)$就无解，所以首先讨论方程什么时候有解。\par
设m的标准分解式是$m=p_1^{\alpha_1} p_2^{\alpha_2}\ldots p_k^{\alpha_k}$,根据定理~\ref{thm:highorcon},二次同余方程等价于方程组$f(x) \equiv 0(mod\ p_i^{\alpha_i}),i=1,2,\ldots,k$.\par 
对于方程$f(x) \equiv 0(mod\ p_i^{\alpha_i}),i \in \{ 1,2,\ldots,k\}$，根据同余的性质($a \equiv b(mod \ m),d \mid m,d>0 \Rightarrow a \equiv b (mod \ d)$)，等价于$f(x) \equiv 0(mod\ p_i),i \in \{ 1,2,\ldots,k\}$，我们将问题转换为考虑此种形式($ax^2+bx+c \equiv 0(mod\ p)$,p为素数)的二次同余方程的解。下面我们对此种形式进行讨论。\par
\begin{enumerate}
	\item 若$p \mid gcd(a,b,c)$，可知x的任何取值都满足方程。
	\item 若$p \nmid gcd(a,b,c)$
	\begin{enumerate}
		\item 若$p \mid a,p \mid b$，则$p \nmid c$,$ax^2+bx+c \equiv 0(mod\ p)$无解。
		\item 若$p \mid a,p \nmid b$,同余方程等价于$bx+c \equiv 0(mod\ p)$,因为gcd(b,p)=1，所以此方程一定有解。具体解法参见前面线性同余方程的求解方法。
		\item 若$p \nmid a,p>2$,则gcd(4a,p)=1\footnote{p>2,p为素数，a和p互素，如果4a和p不互素，那么4和p一定不互素，显然不成立，所以4a和p互素。}，$ax^2+bx+c \equiv 0(mod\ p)$两边同乘4a，配方后得$(2ax+b)^2 -(b^2-4ac) \equiv 0(mod\ p)$，设$y\equiv 2ax+b (mod\ m),d\equiv b^2-4ac(mod\ m)$,原方程可写为$y \equiv d (mod\ m)$,如果$y_0$是其一个解，则$y_0 \equiv 2ax+b (mod\ m)$,$x_0 \equiv (2a)^{-1}(y-b)(mod\ m)$为原方程的一个解。
	\end{enumerate}
\end{enumerate}
通过以上讨论，我们可以得出，对于一般的二次同余方程，我们都可以转化为讨论形如$x^2 \equiv a(mod\ m),gcd(a,m)=1$的二次同余方程的讨论。

\begin{example}
	求解$5x^2-6x+2\equiv (mod\ 13)$.
\end{example}
\begin{solution}
	$gcd(20,13)=1,a=5,b=-6,c=2$\\
	$(2ax+b)^2 \equiv b^2-4ac (mod\ p)$\\
	$y=2ax+b=10x-6$\\
	$d=b^2-4ac=36-4\times 5 \times 2 \equiv -4$\\
	$y^2\equiv -4 \equiv 9(mod\ 13)\Rightarrow y \equiv 3 or 10 (mod\ 13)$,我们可得\\
	$10x-6 \equiv 3(mod\ 13) ~or~ 10x-6\equiv 10(mod\ 13)$,这两个方程可以用前面介绍的方法，也可以用10的逆元为4来求解：\\
	$10x \times 4\equiv 9 \times 4(mod\ 13)\Rightarrow x\equiv 36(mod\ 13)\equiv 10(mod\ 13)$\\
	$10x \times 4\equiv 16 \times 4(mod\ 13)\Rightarrow x\equiv 36(mod\ 13)\equiv 12(mod\ 13)$\\
\end{solution}

\begin{definition}{二次剩余(quadratic residue)}{fubi}
	设m为正整数，若同余式$x^2 \equiv a (mod m),gcd(a,m)=1,$有解，则称a为模m的平方剩余，也叫二次剩余；否则称a为模m的二次非剩余或平方非剩余。
\end{definition}

\begin{example}\\
	求模7的平方剩余。
\end{example}
\begin{solution}\\
	$1^2 \equiv 1 (mod 7)$,$2^2 \equiv 4 (mod 7)$,$3^2 \equiv 2 (mod 7)$,$4^2 \equiv 2 (mod 7)$,$5^2 \equiv 4 (mod 7)$,$6^2 \equiv 1 (mod 7)$,$7^2 \equiv 0 (mod 7)$,$8^2 \equiv 1 (mod 7),9^2 \equiv 4 (mod 7),10^2 \equiv 2 (mod 7),11^2 \equiv 2 (mod 7)$\\
	计算所得余数中与7互素的有1，4，2，可得模7的二次剩余是1，2，4.
\end{solution}



\section{欧拉判别条件}
有时候我们往往需要判断二次同余方程是否有解，欧拉判别条件就是解决这个判定的。\\
\begin{theorem}{欧拉判别条件(Euler's Criterion)\cite{jia2017}}{fubi}
	设p是奇素数，$gcd(a,p)=1$，则:\\
	(1) a是模p的二次剩余的充要条件是$a^{\frac{p-1}{2}} \equiv 1 (mod \ p)$;\\
	(2) a是模p的二次非剩余的充要条件是$a^{\frac{p-1}{2}} \equiv -1 (mod \ p)$;\\
	并且当a是模p的二次剩余时，同余方程$x^2 \equiv a (mod \ p)$恰有两个解。
\end{theorem}

\begin{example}\\
	$i=1,2,\ldots,13$，我们计算$i^2 (mod\ 13)$，但是要注意在二次剩余的定义中互素的条件。然后我们可以检验一下上面的欧拉判别条件的正确性。
\end{example}

\begin{example}\\
	8是不是模17的平方剩余？
\end{example}
\begin{solution}\\
	gcd(8,17)=1,17为奇素数\\
	$8^{(17-1)/2}=8^8=16777216 \equiv 1 (mod 7)$,因此8是模17的平方剩余。
\end{solution}

\begin{example}\\
	137是不是模227的平方剩余？
\end{example}
\begin{solution}\\
	227是奇素数，gcd(137,227)=1\\
	$137^{(227-1)/2}=137^{113} (mod\ 227)$\\
	$\because 137^2=18769 (mod 227) \equiv 155 (mod\ 227)$\\
	$\therefore 137^{113} (mod 227) \equiv 155^{56} \cdot 137 (mod\ 227)$\\
	$\because 155^2=24025 (mod 227) \equiv 190 (mod\ 227)$\\
	$\therefore 137^{113} (mod 227) \equiv 190^{28} \cdot 137 (mod\ 227)$\\
	$\because 190^2=36100 (mod 227) \equiv 7 (mod 227)$\\
	$\therefore 137^{113} (mod 227) \equiv 7^{14} \cdot 137 (mod\ 227)$\\
	$\because 7^{14}=49^7=49^6 \cdot 49 = 131^3 \cdot 49 \equiv 136 \cdot 131 \cdot 49(mod\ 227)$\\
	$\therefore 137^{113} \equiv 136 \cdot 131 \cdot 49 \cdot 137 (mod\ 227) $\\
	$136 \cdot 131 \equiv 17816 \equiv 110 (mod\ 227)$\\
	$110 \cdot 49 = 5390 \equiv 169 (mod\ 227)$\\
	$169 \cdot 137 = 23153 \equiv 226\equiv -1 (mod\ 227)$\\
	由于余数为-1，故137是模227的平方非剩余。
\end{solution}
我们也可以用SageMath编写程序来判断137是否是模227的二次剩余。
\begin{SageMath}{判断二次剩余}
	\begin{verbatim}
	sage: if mod(227,2)==0:
	....: print "227 is odd"
	....: elif is_prime(227):
	....: print "227 is prime"
	....: if mod(137^((227-1)/2),227)==1:
	....:   print "137 is quadratic residue of module 227"
	....: else:
	....:   print "137 is not quadratic residue of module 227"
	....: else:
	....:   print "227 is not prime"
	....:
	227 is prime
	137 is not quadratic residue of module 227
	sage:
	\end{verbatim}
\end{SageMath}

\section{勒让德符号}
从上面的计算我们基本可以看出，当p比较大时，用欧拉判定方法来判定一个数是否为p的二次剩余时，计算量很大。引入Legendre符号，可以给出一种更有效的判定方法。
\subsection{概念}
\begin{definition}{勒让德符号(Legendre symbol)\cite{jia2017}}
	设p是奇素数，$gcd(a,p)=1$，定义勒让德（legendre）符号为：\\
	\begin{equation}
	\begin{bmatrix}
	\frac{a}{p}
	\end{bmatrix}
	=
	\begin{cases}
	1,\text{若a是模p的二次剩余}\\
	-1,\text{若a是模p的二次非剩余}
	\end{cases}
	\end{equation}
\end{definition}
下面给出\cite{qing2018}中的Legendre符号定义的方法，请注意比较。
\begin{definition}{勒让德符号(Legendre symbol)}
	设p是奇素数，a是整数，定义勒让德（legendre）符号为：\\
	\begin{equation}
	\begin{bmatrix}
	\frac{a}{p}
	\end{bmatrix}
	=
	\begin{cases}
	1,\text{若a是模p的二次剩余}\\
	-1,\text{若a是模p的二次非剩余}\\
	0,\text{若p|a}
	\end{cases}
	\end{equation}
\end{definition}

\begin{example}\\
	求13的Legendre符号。
\end{example}
\begin{solution}\\
	可以通过计算得知1，3，4，9，10，12是模13的二次剩余，2，5，6，7，8，11为模13的二次非剩余。所以我们有：\\
	\begin{equation}
	\begin{bmatrix}
	\frac{1}{13}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{3}{13}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{4}{13}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{9}{13}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{10}{13}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{12}{13}
	\end{bmatrix}=1
	\end{equation}
	
	\begin{equation}
	\begin{bmatrix}
	\frac{2}{13}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{5}{13}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{6}{13}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{7}{13}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{8}{13}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{11}{13}
	\end{bmatrix}=-1
	\end{equation}
\end{solution}
利用勒让德符号，我们可以将欧拉判别条件利用勒让德符号进行改写。
\begin{theorem}{欧拉判别条件的勒让德符号表示\cite{jia2017}}{fubi}
	设p是齐素数，a是与p互素的整数，则$[\frac{a}{p}] \equiv a^{\frac{p-1}{2}} (mod\ p)$.显然$[\frac{1}{p}]=1$.
\end{theorem}

\subsection{勒让德符号的运算律}
\begin{theorem}{Legendre符号的性质\cite{jia2017}}{fubi}
	设p是齐素数，a,b都是与p互素的整数，则有：\\
	(1)若$a \equiv b  (mod\ p) \Rightarrow \begin{bmatrix}
	\frac{a}{p}
	\end{bmatrix} =\begin{bmatrix}
	\frac{b}{p}
	\end{bmatrix}$\\
	(2)$\begin{bmatrix}
	\frac{ab}{p}
	\end{bmatrix} =\begin{bmatrix}
	\frac{a}{p}
	\end{bmatrix}
	\begin{bmatrix}
	\frac{b}{p}
	\end{bmatrix}
	$\\
	(3)$\begin{bmatrix}
	\frac{a^2}{p}
	\end{bmatrix}=1$\\
\end{theorem}

\begin{theorem}{\cite{jia2017}}{fubi}\label{minuspleng}
	设p是齐素数，我们有$[\frac{-1}{p}]=(-1)^{\frac{p-1}{2}}=\begin{cases}
		1,p\equiv 1 (mod\ 4)\\
		-1,p \equiv 3(mod\ 4)
	\end{cases}$.
\end{theorem}

\begin{theorem}{\cite{qing2018}}{fubi}\label{twopleng}
	设p是齐素数，则$[\frac{2}{p}]=(-1)^{\frac{p^2-1}{8}}$.
\end{theorem}

\subsection{勒让德符号的计算}

\begin{theorem}{二次剩余的高斯引理\cite{jia2017}}
	设p是奇素数，a是与p互素的整数，如果$\frac{p-1}{2}$个整数$a\times 1,a\times 2,a\times 3, \ldots ,a \times \frac{p-1}{2}$模p后得到的最小正剩余中大于$\frac{p}{2}$的个数是m，则
	$\begin{bmatrix}
	\frac{a}{p}
	\end{bmatrix}
	=(-1)^m$
\end{theorem}
\begin{example}\cite{jia2017}\\
	利用高斯引理判断5是否为模13的二次剩余。
\end{example}
\begin{solution}\\
	13是奇素数，5和13互素，$(13-1)/2 =6$，可得整数序列5，10，15，20，25，30，这些数模13后得：5，10，2，7，12，4，其中大于13/2的数有10，7，12，共3个(m=3)，那么根据高斯引理有：\\
	$\begin{bmatrix}
	\frac{5}{13}
	\end{bmatrix}
	=(-1)^3=-1$\\
	5是模13的二次非剩余。
\end{solution}

\begin{theorem}{二次互反率(quadratic reciprocity law )\cite{jia2017}}
	设p、q是奇素数，$p\neq q$，则
	$
	\begin{bmatrix}
	\frac{p}{q}
	\end{bmatrix}
	\begin{bmatrix}
	\frac{q}{p}
	\end{bmatrix}
	= (-1)^{\frac{p-1}{2} \frac{q-1}{2}}
	$。
\end{theorem}
在实际应用中，我们有时也把二次互反率写为：
$
\begin{bmatrix}
\frac{q}{p}
\end{bmatrix}=(-1)^{\frac{p-1}{2} \frac{q-1}{2}}
\begin{bmatrix}
\frac{p}{q}
\end{bmatrix}
$
\begin{example}\cite{jia2017}\\
	3是否为模17的二次剩余。
\end{example}
\begin{solution}\\
	由二次互反率，有：\\
	$
	\begin{bmatrix}
	\frac{3}{17}
	\end{bmatrix}=(-1)^{\frac{3-1}{2} \frac{17-1}{2}}
	\begin{bmatrix}
	\frac{17}{3}
	\end{bmatrix}
	=
	\begin{bmatrix}
	\frac{17}{3}
	\end{bmatrix}$\\
	$\because 17=6\times 3-1 \equiv -1 (mod\ 3)$\\
	$\therefore [\frac{17}{3}] =[\frac{-1}{3}]$\\
	根据定理~\ref{minuspleng}，我们有：\\
	$[\frac{-1}{3}]=(-1)^{\frac{3-1}{2}}=-1	$\\
	故3是模17的二次非剩余。
\end{solution}

\begin{example}\cite{qing2018}\\
	同余方程$x^2 \equiv 137 (mod 227)$是否有解？
\end{example}
\begin{solution}
	227是素数，则:\\
	$
	\begin{bmatrix}
	\frac{137}{227}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{-90}{227}
	\end{bmatrix}=
	\begin{bmatrix}
	\frac{-1}{227}
	\end{bmatrix}
	\begin{bmatrix}
	\frac{2 \cdot 3^2 \cdot 5}{227}
	\end{bmatrix}=
	-\begin{bmatrix}
	\frac{2}{227}
	\end{bmatrix}\begin{bmatrix}
	\frac{5}{227}
	\end{bmatrix}
	$\\
	根据定理~\ref{twopleng},有$
	\begin{bmatrix}
	\frac{2}{227}
	\end{bmatrix}=(-1)^{\frac{227^1 -1}{8}}=(-1)^{\frac{226\cdot 228}{8}}=-1
	$\\
	根据二次互反律有，$
	\begin{bmatrix}
	\frac{5}{227}
	\end{bmatrix}=(-1)^{\frac{5 -1}{2} \frac{227-1}{2}}\begin{bmatrix}
	\frac{227}{5}
	\end{bmatrix}=\begin{bmatrix}
	\frac{227}{5}
	\end{bmatrix}=\begin{bmatrix}
	\frac{2}{5}
	\end{bmatrix}=
	=(-1)^{\frac{5^2-1}{8}}=-1
	$\\
	因此，$\begin{bmatrix}
	\frac{137}{227}
	\end{bmatrix}=-1$,也就是说原同余方程无解。
\end{solution}

\section{雅克比符号(Jacobi Symbol)}
我们在利用勒让德符号判断二次同余方程是否有解时，通常需要将符号上方的数分解成标准分解式，而把一数分解成标准分解式是没有什么一般方法的，因此，利用勒让德符号来判断实际计算时，还有一定程度的缺点。引入雅可比符号就是为了去掉这一缺点。\cite{min2003}\par
\subsection{概念}
\begin{definition}{雅克比符号(Jacobi Symbol)}
	设正奇数$m=p_1  p_2 \ldots p_r$是奇素数$p_i \ (i=1,2,\ldots ,r)$的乘积，定义雅克比符号为
	$
	\begin{pmatrix}
	\frac{a}{m}
	\end{pmatrix}
	=
	\begin{bmatrix}
	\frac{a}{p_1}
	\end{bmatrix}
	\begin{bmatrix}
	\frac{a}{p_2}
	\end{bmatrix}
	\ldots
	\begin{bmatrix}
	\frac{a}{p_r}
	\end{bmatrix}
	$。
\end{definition}
雅可比符号是用勒让德符号定义的，但是，雅可比符号将Legendre符号从奇素数的限制，扩大到正奇数。
“扩大后其意义也发生了变化，如果a对p的勒让德符号为1，可知a是模p的二次剩余，但当a对m的雅可比符号为1时，却不能得到a是模m的二次剩余这个结论。\par
雅可比符号的好处就是它一方面具有很多与勒让德符号一样的性质，当r=1是，雅可比符号和勒让德符号相等，另一方面，他并没有限制m必需是素数，因此要想计算勒让德符号的值，只须把他看成雅可比符号来计算。在计算雅可比符号值时，由于不用考虑m是不是素数，所以在实际计算上就非常方便了，并且利用雅可比符号最后一定能把勒让德符号的值计算出来。”\cite{min2003}(第88页)\par

